\documentclass[15pt,a4paper]{article}

%use the english line for english reports
%usepackage[english]{babel}
\usepackage[portuguese]{babel}
\usepackage[utf8]{inputenc}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[table]{xcolor}

\begin{document}

\setlength{\textwidth}{16cm}
\setlength{\textheight}{22cm}

\title{\Huge\textbf{Cannon}\linebreak\linebreak\linebreak
\Large\textbf{Relatório Final}\linebreak\linebreak
\includegraphics[height=6cm, width=7cm]{feup.pdf}\linebreak \linebreak
\Large{Mestrado Integrado em Engenharia Informática e Computação} \linebreak \linebreak
\Large{Programação em Lógica}\linebreak
}

\author{\textbf{Grupo 04:}\\ Miguel Regala - 09128 \\ José Bateira - 10133 \\\linebreak\linebreak \\
 \\ Faculdade de Engenharia da Universidade do Porto \\ Rua Roberto Frias, s\/n, 4200-465 Porto, Portugal \linebreak\linebreak\linebreak
\linebreak\linebreak\vspace{1cm}}
%\date{Junho de 2007}
\maketitle
\thispagestyle{empty}

%************************************************************************************************
%************************************************************************************************

\newpage

\section*{Resumo}
Este relatório tem o objectivo de documentar a implementação final do jogo de tabuleiro conhecido por \textit{Cannon: The Emperor’s Game}, na linguagem de Prolog.  

Pretende-se descrever o que foi implementado e o estado global do trabalho, em comparação com o que foi proposto no primeiro relatório.

\newpage

\tableofcontents

%************************************************************************************************
%************************************************************************************************

%*************************************************************************************************
%************************************************************************************************

\newpage

\section{Introdução}
\subsection{Motivação}
O \textit{Cannon} é um jogo com regras muito simples e que, devido a isso, obriga o jogador a concentrar-se nas estratégias complexas que podem ser formadas. Para além do mais, o jogo em si é muito interessante e único, por combinar características de vários jogos de tabuleiro.
Os autores deste trabalho desconheciam o jogo e após algumas pesquisas na Web puderam constatar que existem poucas aplicações do jogo que lhe façam justiça, quer em termos de qualidade como em características open-source, sendo mais uma motivação extra para realizar um bom trabalho. 

\subsection{Objectivos}
O objectivo principal deste trabalho é a familiarização com a linguagem de programação lógica,     o Prolog e adquirir um entendimento das diferenças que existem entre este tipo de programação e programação funcional.

\subsection{Estrutura do relatório}
Este é o relatório final do trabalho. Na secção que se segue descrevemos o problema e o jogo em si. De seguida discutimos pormenores de implementação e aprofundamos as soluções usadas.

\section{Descrição do Problema}
\subsection{Introdução}
O \textit{Cannon} foi publicado pela primeira vez em 2003. É um jogo de tabuleiro de duração curta, tirando grandes inspirações nos jogos de tabuleiros tradicionais como as damas e o xadrez. É jogado por duas pessoas.

\subsection{Regras do jogo}
As regras são muito simples. Cada jogador tem direito a 15 peças, denominadas de \textit{Soldados} e a mais uma, a \textit{Base}. O \textit{Canhão}, não é uma peça por si só, mas uma combinação de 3 \textit{Soldados}, dispostos em linha ortogonal ou oblíqua. Os movimentos das peças são descritos a seguir.

O objectivo do jogo é o de conquistar a peça \textit{Base} do adversário, ou eliminando todos os \textit{Soldados}. Analogamente às damas, a conquista de uma peça é feita através de uma jogada em que o destino seja uma célula adjacente preenchida por um \textit{Soldado} inimigo, ou disparando uma bala do \textit{Canhão} a uma curta distância.

\subsection{Tipos de peças}
\subsubsection{Soldados}
O \textit{Soldado} é a unidade básica do jogo. Esta peça pode mover-se da seguintes formas:

\begin{figure}[h!]
\begin{center}
%escolher entre uma das seguintes três linhas:
%\includegraphics[height=20cm,width=15cm]{path relativo da imagem}
\includegraphics[scale=0.5]{graphics/soldiermove.png}
%\includegraphics{path relativo da imagem}
\caption{Para a frente, uma célula, nas direcções N, NE, NW}
\label{fig:soldiermove}
\end{center}
\end{figure}

Num caso especial, o \textit{Soldado} pode recuar. Isto acontece quando um Soldado inimigo se encontra numa célula adjacente.

\begin{figure}[h!]
\begin{center}
%escolher entre uma das seguintes três linhas:
%\includegraphics[height=20cm,width=15cm]{path relativo da imagem}
\includegraphics[scale=0.5]{graphics/soldierRetreat.png}
%\includegraphics{path relativo da imagem}
\caption{Para trás, 2 células, obrigatoriamente desocupadas}
\label{fig:soldiermove2}
\end{center}
\end{figure}

\subsubsection{Canhões}
Quando temos 3 peças adjacentes, dispostas obliquamente ou de forma ortogonal, estas representam um \textit{Canhão} que permitem ao jogador “matar” \textit{Soldados} inimigos que coincidam com a linha formada pelas peças, com um alcance de 2 a 3 células.

\begin{figure}[h!]
\begin{center}
%escolher entre uma das seguintes três linhas:
%\includegraphics[height=20cm,width=15cm]{path relativo da imagem}
\includegraphics[scale=0.5]{graphics/cannonshot.png}
%\includegraphics{path relativo da imagem}
\caption{Alcance de 2 a 3 células}
\label{fig:cannon}
\end{center}
\end{figure}

A formação \textit{Canhão} pode deslocar-se, uma célula, ao longo da linha que é definida:
\begin{figure}[h!]
\begin{center}
%escolher entre uma das seguintes três linhas:
%\includegraphics[height=20cm,width=15cm]{path relativo da imagem}
\includegraphics[scale=0.5]{graphics/cannonshift.png}
%\includegraphics{path relativo da imagem}
\caption{Movimento tipo “lagarta” do \textit{Canhão}}
\label{fig:cannon2}
\end{center}
\end{figure}

\subsubsection{Cidades}
As cidades são representadas pelas peças quadradas dispostas inicialmente na primeira linha de cada jogador.

\section{Arquitectura do Sistema}

\subsection{Impressão do tabuleiro}
A impressão do tabuleiro é feita num ficheiro à parte, \textit{print.pl}, onde são definidos os vários tabuleiros que podem ser usados e implementadas os predicados para percorrer e converter da representação interna para a visualização.

\subsection{Lógica do jogo}
A lógica do jogo é toda armazenada num único ficheiro, \textit{main.pl}. No início consideramos em modularizar o jogo mas não o conseguimos implementar.

\subsection{Visualização em OpenGL}
Para construirmos o programa externo \textit{visualizador}, que irá interpretar o estado interno do jogo, vamos utilizar comunicação em sockets, seguindo uma abordagem cliente-servidor. 
O servidor, será o programa em Prolog, que permitirá vários clientes ligarem-se ao servidor e correr cada um deles uma instância diferente do jogo.

\subsubsection{Servidor}
Os procedimentos fundamentais do servidor serão os seguintes:
\\ 
\newline
	{\fontencoding{OT1}\fontfamily{pcr}\selectfont 
    receiveMessage(Client, Message)\\
    sendMessage(Client, Message, Ack)\\
    initiateConnection(Client)\\
    terminateConnection(Client)\\
    initiateGame(Client , Game)\\
    closeGame(Client, Game)\\
	}
\newline
O servidor estará continuamente à escuta num porto definido, até algum cliente se ligar. Nessa altura, estabelece-se uma ligação e inicia-se um jogo.


\section{Módulo de Lógica do Jogo}
Descrever o projecto e implementação do módulo Prolog, incluindo a forma de representação do estado do tabuleiro,  verificação do cumprimento das regras do jogo, determinação do final do jogo e cálculo das jogadas a realizar pelo computador  utilizando diversos níveis de jogo.

\subsection{Representação do Estado do Jogo}
Como é trivial neste tipo de casos, em que é necessário representar uma 
matriz de valores para representar o tabuleiro, utilizou-se uma lista de listas. Neste caso, uma lista de dez elementos que por sua vez tem nova lista de dez elementos. A ordem de acesso a um elemento é do tipo.

Este é o primeiro estado do jogo. A configuração das peças é fixa e a única peça de qual os jogadores podem alterar a sua posição é a cidade. Estas posições são especificadas na primeira jogada, recorrendo ao predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont first\_play}.

Como já foi referido, uma das vantagens deste jogo é a pouca diversidade de peças, o que ajuda na implementação do programa. Ainda assim, a tradução dos símbolos em peças está definida como a seguinte:

\begin{table}[t]
\centering
\begin{tabular}{|l|c|}
\hline
Peça & Representação \\
\hline
Vazio & 0x00 \\
Soldado A & 0x01 \\
Soldado B & 0x02 \\
Canhão A & 0x03 \\
Canhão B & 0x04 \\
Base A & 0x05 \\
Base B & 0x06 \\

\hline
\end{tabular}
\caption{representação interna}
\label{tab:template}
\end{table}
 
\subsection{Visualização do Estado do Jogo}
A visualização do estado de jogo é feita em \textit{main.pl}, pelo predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont printBoard}.

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.5]{graphics/board.png}
\caption{tabuleiro na primeira jogada}
\label{fig:soldiermove}
\end{center}
\end{figure}

Este predicado limita-se a percorrer cada célula em cada linha e interpreta o seu valor, imprimindo um caracter correspondente.
É preciso ainda apontar que a cada nova ronda o tabuleiro é rodado, pelo que os jogadores jogam sempre usando a mesma perspectiva: de baixo para cima. De uma forma semelhante, as peças inimigas são sempre representadas por um asterisco (*) e as próprias por uma cruz (x).

\subsection{Validação do input}
Em todas as decisões que o jogador tem que tomar e que precisa de escolher uma opção, a sua escolha é validada por uma função que limita os valores que a variável \textit{Input} pode tomar, garantindo que as escolhas são sempre válidas, ou seja que constam das escolhas possíveis.
A validação é feita recorrendo aos predicados {\fontencoding{OT1}\fontfamily{pcr}\selectfont getX} e {\fontencoding{OT1}\fontfamily{pcr}\selectfont getY} que limitam os valores que podem ser usados.
Por sua vez, estes predicados são chamados pelos predicados {\fontencoding{OT1}\fontfamily{pcr}\selectfont prompt}, como {\fontencoding{OT1}\fontfamily{pcr}\selectfont prompt\_play} e {\fontencoding{OT1}\fontfamily{pcr}\selectfont prompt\_base}: estes pedem e validam as coordenadas da jogada de origem e destino introduzidas pelo jogador.

\subsection{Validação de Jogadas} 
A validação de jogadas é feita recorrendo ao predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont check\_play}.
Primeiro, verifica se a coordenada de origem corresponde a uma peça do jogador que está a jogar. De seguida, verifica a existência ou não se a peça selecionada é um \textit{Canhão} e passa essa informação a {\fontencoding{OT1}\fontfamily{pcr}\selectfont valid\_move}.
Dependendo se é um \textit{Canhão} ou \textit{Soldado} são feitas verificações diferentes. {\fontencoding{OT1}\fontfamily{pcr}\selectfont cannon\_action} verifica todas as jogadas possíveis que um \textit{Canhão} pode fazer, seja um disparo ou movimento. Se não é possível fazer nenhuma jogada então o programa avança experimentando os movimentos normais de um \textit{Soldado}.

\subsection{ Verificação de movimentos }
\subsubsection{ \textit{Soldados} }
O predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont walk\_moves} tem como função verificar se o movimento inserido pelo utilizador é válido. Este limita-se a verificar todos os movimentos possíveis até algum ser possível. A forma como fazemos a verificação de um movimento é partir da célula de origem e incrementar o par de posições X e de Y, verificando que as células intermédias estão vazias, até chegar à célula de destino.
\subsubsection{ \textit{Canhões} }
O tratamento dos movimentos dos \textit{Canhões} é mais peculiar, isto porque podem mover-se e disparar à distância. A solução que encontramos foi de dar prioridade ao disparo, depois ao movimento do canhão como um todo e por fim o movimento do soldado selecionado, integrante do canhão.
Para um disparo ser validado, utiliza-se o predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont cannon\_fire}. Mais uma vez, este tenta verificar se é possível fazer qualquer disparo, com os dados submetidos pelo utilizador. Essa verificação é feita em duas fases: para cada tipo de disparo, o predicado correspondente verifica se o \textit{Canhão} esta na posição necessária (Horizontal, Vertical, etc) e se a peça selecionada do canhão é a da ponta - se não for, aplica uma chamada recursiva a si própria, até estarmos a tratar a ultima peça do canhão. Por fim, de forma análoga a um movimento tenta chegar à célula de destino: se conseguir, o disparo é válido e a peça apontada é eliminada.
Caso um disparo não consegue ser efectuado, tenta-se mover todo o \textit{canhão}, recorrendo ao predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont cannon\_moves}. Primeiro identifica o tipo de movimento do canhão, horizontal, vertical ou diagonal e chama os predicados correspondentes.  O formato genérico destes é primeiro selecionar a peça da ponta do \textit{Canhão} e depois verificar se para o dado movimento, o \textit{Canhão} esta no formato necessário (e.g um movimento na horizontal implica que o \textit{Canhão} esteja na horizontal).
Se nenhum destes predicados tiver sucesso, o programa tenta a verificação normal do movimento de um soldado.

\subsection{Execução de Jogadas}
A execução da jogada é feita imediatamente após a validação. É usada uma função genérica {\fontencoding{OT1}\fontfamily{pcr}\selectfont update\_or\_attack} que primeiro tenta eliminar alguma peça que esteja na célula de destino e apenas depois actualiza a posição da peça atacante. A actualização desta peça é trivial: inseri-mo-la na nova posição e eliminamos a posição antiga.

\subsection{Final do Jogo}
No final de cada jogada o programa confere se alguma das condições de final do jogo foi atingida, através do predicado {\fontencoding{OT1}\fontfamily{pcr}\selectfont check\_endgame}. A primeira condição de final de jogo é a destruição da base inimiga, pelo que a basta procurar na nona linha do tabuleiro. A outra condição é a eliminação de todas as peças do jogador adversário. Tanto uma como outra são condições necessárias e suficientes, pelo que basta uma ocorrer para o jogo terminar.

\subsection{Predicados Auxiliares}
\subsubsection{ {\fontencoding{OT1}\fontfamily{pcr}\selectfont Rotate\_Board}}
Como o nome indica este predicado tem a responsabilidade de inverter o tabuleiro de jogo, de forma a que cada jogador visualize sempre o jogo de baixo para cima. A forma como o fizemos foi criarmos um novo tabuleiro a partir do original, fazendo com que a nova primeira linha seja igual à ultima coluna, e assim sucessivamente. Desta forma o tabuleiro roda noventa graus. Para termos uma inversão completa, realizamos o mesmo procedimento.

\subsubsection{ {\fontencoding{OT1}\fontfamily{pcr}\selectfont Insert\_Piece}}
Este procedimento é a base da manipulação do tabuleiro. Funciona percorrendo o tabuleiro, gravando o que foi percorrido numa variável temporária, até chegar à linha Y e à célula X. Quando isso acontece, descarta o valor actual da célula e insere um novo, passado como argumento do predicado. Depois limita-se a continuar a percorrer o tabuleiro, anexando-o ao á variável temporária, efectivamente construindo um tabuleiro igual ao original com apenas uma célula modificada.

\section{Conclusões e Perspectivas de Desenvolvimento}
\subsection{Percentagem de trabalho concluído}
Estimamos que tenhamos concluído cerca de 85\% do trabalho proposto, sendo os 15\% restantes referentes ao módulo de inteligência artificial, não implementada.
Dado que em termos funcionais o jogo é irrepreensível, podemos passar à implementação do visualizador sem problemas.

\subsection{Conclusões}
O primeiro facto a retirar deste trabalho, para além dos conhecimentos obtidos é a gestão de tempo. O nosso trabalho foi entregue após a data por não termos conseguido acompanhar e desenvolver o trabalho seguindo as datas de limite.
Certamente, isso é a primeira coisa a corrigir. Também podemos apontar que o código desenvolvido podia ser repensado em algumas secções, de forma a ter predicados mais genéricos e evitar a proliferação de código repetido.
Neste momento, o nosso objectivo é começar o mais cedo possível o desenvolvimento da parte seguinte deste trabalho, de forma a poder recuperar o tempo e os pontos perdidos.

\clearpage
\addcontentsline{toc}{section}{Bibliografia}
\renewcommand\refname{Bibliografia}
\bibliographystyle{plain}
\bibliography{myrefs}


\end{document}
